home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / scope / 076-100 / scopedisk91 / uncomp16 / ucomp16.c < prev   
Encoding:
C/C++ Source or Header  |  1995-03-19  |  7.7 KB  |  242 lines
  1. #define PBITS 16
  2. #define BITS PBITS
  3.  
  4. unsigned       char magic_header[] = { 
  5.        "\037\235" };   /* 1F 9D */
  6.  
  7. /* Defines for third byte of header */
  8. #define BIT_MASK       0x1f
  9. #define BLOCK_MASK     0x80
  10. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  11. a fourth header byte (for expansion).
  12. */
  13. #define INIT_BITS 9            /* initial number of bits/code */
  14.  
  15. #include <stdio.h>
  16.  
  17. int n_bits;                            /* number of bits/code */
  18. int maxbits = BITS;                    /* user settable max # bits/code */
  19. long   int maxcode;                    /* maximum code, given n_bits */
  20. long   int maxmaxcode = 1 << BITS;     /* should NEVER generate this code */
  21. # define MAXCODE(n_bits)       ((1 << (n_bits)) - 1)
  22.  
  23. /*
  24. * One code could conceivably represent (1<<BITS) characters, but
  25. * to get a code of length N requires an input string of at least
  26. * N*(N-1)/2 characters.  With 5000 chars in the stack, an input
  27. * file would have to contain a 25Mb string of a single character.
  28. * This seems unlikely.
  29. */
  30. # define MAXSTACK    8000              /* size of output stack */
  31.  
  32. unsigned short tab_prefix [69001];
  33. unsigned       char    tab_suffix[1<<BITS];    /* last char in this entry */
  34.  
  35. long   int free_ent = 0;                       /* first unused entry */
  36. int exit_stat = 0;
  37.  
  38. long   int getcode();
  39.  
  40. /*
  41. * block compression parameters -- after all codes are used up,
  42. * and compression rate changes, start over.
  43. */
  44. int block_compress = BLOCK_MASK;
  45. int clear_flg = 0;
  46. /*
  47. * the next two codes should not be changed lightly, as they must not
  48. * lie within the contiguous general code space.
  49. */
  50. #define FIRST  257     /* first free entry */
  51. #define        CLEAR   256     /* table clear output code */
  52.  
  53. main()
  54. {
  55.        if(maxbits < INIT_BITS) maxbits = INIT_BITS;
  56.        if (maxbits > BITS) maxbits = BITS;
  57.        maxmaxcode = 1 << maxbits;
  58.  
  59.        exit_stat = 0;
  60.        /* Check the magic number */
  61.        if ((getchar() != (magic_header[0] & 0xFF))
  62.            || (getchar() != (magic_header[1] & 0xFF))) {
  63.                fprintf(stderr,"not in compressed format\n");
  64.                exit(1);
  65.        }
  66.        maxbits = getchar();    /* set -b from file */
  67.        block_compress = maxbits & BLOCK_MASK;
  68.        maxbits &= BIT_MASK;
  69.        maxmaxcode = 1 << maxbits;
  70.        if(maxbits > BITS) {
  71.                fprintf(stderr,
  72.                    "compressed with %d bits, can only handle %d bits\n",
  73.                    maxbits, BITS);
  74.                exit(1);
  75.        }
  76.        decompress();
  77.        exit(exit_stat);
  78. }
  79. unsigned       char rmask[9] = {
  80.        0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  81. decompress() {
  82.        register int stack_top = MAXSTACK;
  83.        register long   int code, oldcode, incode;
  84.        register int finchar;
  85.        char stack[MAXSTACK];
  86.  
  87.        /*
  88. * As above, initialize the first 256 entries in the table.
  89. */
  90.        maxcode = MAXCODE(n_bits = INIT_BITS);
  91.        for ( code = 255; code >= 0; code-- ) {
  92.                tab_prefix[code] = 0;
  93.                tab_suffix[code] = (unsigned    char)code;
  94.        }
  95.        free_ent = ((block_compress) ? FIRST : 256 );
  96.  
  97.        finchar = oldcode = getcode();
  98.        putchar( (char)finchar );               /* first code must be 8 bits = char */
  99.  
  100.        while ( (code = getcode()) != -1 ) {
  101.  
  102.                if ( (code == CLEAR) && block_compress ) {
  103.                        for ( code = 255; code > 0; code -= 4 ) {
  104.                                tab_prefix [code-3] = 0;
  105.                                tab_prefix [code-2] = 0;
  106.                                tab_prefix [code-1] = 0;
  107.                                tab_prefix [code] = 0;
  108.                        }
  109.                        clear_flg = 1;
  110.                        free_ent = FIRST - 1;
  111.                        if ( (code = getcode ()) == -1 )        /* O, untimely death! */
  112.                                break;
  113.                }
  114.                incode = code;
  115.                /*
  116. * Special case for KwKwK string.
  117. */
  118.                if ( code >= free_ent ) {
  119.                        stack[--stack_top] = finchar;
  120.                        code = oldcode;
  121.                }
  122.  
  123.                /*
  124. * Generate output characters in reverse order
  125. */
  126.                while ( code >= 256 ) {
  127.                        stack[--stack_top] = tab_suffix[code];
  128.                        code = tab_prefix[code];
  129.                }
  130.                stack[--stack_top] = finchar = tab_suffix[code];
  131.  
  132.                /*
  133. * And put them out in forward order
  134. */
  135.                for ( ; stack_top < MAXSTACK; stack_top++ )
  136.                        putchar(stack[stack_top]);
  137.                if (ferror(stdout))
  138.                        writeerr ( );
  139.                stack_top = MAXSTACK;
  140.  
  141.                /*
  142. * Generate the new entry.
  143. */
  144.                if ( (code=free_ent) < maxmaxcode ) {
  145.                        tab_prefix[code] = (unsigned short)oldcode;
  146.                        tab_suffix[code] = finchar;
  147.                        free_ent = code+1;
  148.                }
  149.                /*
  150. * Remember previous code.
  151. */
  152.                oldcode = incode;
  153.        }
  154.        fflush( stdout );
  155.        if(ferror(stdout))
  156.                writeerr();
  157. }
  158.  
  159.  
  160. /*****************************************************************
  161. * TAG( getcode )
  162. *
  163. * Read one code from the standard input.  If EOF, return -1.
  164. * Inputs:
  165. *      stdin
  166. * Outputs:
  167. *      code or -1 is returned.
  168. */
  169.  
  170. long   int
  171. getcode() {
  172.        /*
  173. * On the VAX, it is important to have the register declarations
  174. * in exactly the order given, or the asm will break.
  175. */
  176.        register long   int code;
  177.        static int offset = 0, size = 0;
  178.        static unsigned char buf[BITS];
  179.        register int r_off, bits;
  180.        register unsigned       char *bp = buf;
  181.  
  182.        if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) {
  183.                /*
  184. * If the next entry will be too big for the current code
  185. * size, then we must increase the size.  This implies reading
  186. * a new buffer full, too.
  187. */
  188.                if ( free_ent > maxcode ) {
  189.                        n_bits++;
  190.                        if ( n_bits == maxbits )
  191.                                maxcode = maxmaxcode;   /* won't get any bigger now */
  192.                        else
  193.                                maxcode = MAXCODE(n_bits);
  194.                }
  195.                if ( clear_flg > 0) {
  196.                        maxcode = MAXCODE (n_bits = INIT_BITS);
  197.                        clear_flg = 0;
  198.                }
  199.                size = fread( buf, 1, n_bits, stdin );
  200.                if ( size <= 0 )
  201.                        return -1;                      /* end of file */
  202.                offset = 0;
  203.                /* Round size down to integral number of codes */
  204.                size = (size << 3) - (n_bits - 1);
  205.        }
  206.        r_off = offset;
  207.        bits = n_bits;
  208.        /*
  209. * Get to the first byte.
  210. */
  211.        bp += (r_off >> 3);
  212.        r_off &= 7;
  213.        /* Get first part (low order bits) */
  214.        code = (*bp++ >> r_off);
  215.        bits -= (8 - r_off);
  216.        r_off = 8 - r_off;              /* now, offset into code word */
  217.        /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  218.        if ( bits >= 8 ) {
  219.                code |= *bp++ << r_off;
  220.                r_off += 8;
  221.                bits -= 8;
  222.        }
  223.        /* high order bits. */
  224.        code |= (*bp & rmask[bits]) << r_off;
  225.        offset += n_bits;
  226.  
  227.        return code;
  228. }
  229. /*****************************************************************
  230. * TAG( writeerr )
  231. *
  232. * Exits with a message.  We only check for write errors often enough
  233. * to avoid a lot of "file system full" messages, not on every write.
  234. * ferror() check after fflush will catch any others (I trust).
  235. *
  236. */
  237.  
  238. writeerr()
  239. {
  240.        exit ( 1 );
  241. }
  242.